// author by welong
// zuowl@qq.com
// 2014-09-10  10:33
// PAT basic 1025

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//#define DEBUG

int count_new = 0;

typedef struct Node
{
	int icurr;
	int idata;
	int inext;

	struct Node *next;
	struct Node *prev;
}node, *pnode;

void init_list(pnode head)
{
	head->icurr = 0;
	head->idata = 0;
	head->inext = 0;

	head->prev = NULL;
	head->next = NULL;
}

void modify(pnode p)
{
	p->prev->next = p->next;

	if(p->next != NULL)
		p->next->prev = p->prev;
}

pnode insert_back(pnode back, pnode newn)
{
	back->next = newn;
	newn->prev = back;
	newn->next = NULL;
	
	return newn;
}

#ifdef DEBUG
void print_list(pnode head);
void debug_print(pnode input, pnode output);
#endif

/* some nodes are not in the linked list, cause test site 6 error */
int main(int argc, char **argv)
{
	int i, j, k, temp;
	int start_addr, count, rev;
	
	node  input, output;
	pnode p, ptemp, back_i, back_o, *array;

	scanf("%d%d%d", &start_addr, &count, &rev);
	temp = start_addr;

	/*************************** input ******************************/
	init_list(&input);
	init_list(&output);

	temp = start_addr;
	back_i = &input;
	back_o = &output;

	for(i = 0; i < count; i++)
	{
		p = (pnode)malloc(sizeof(node));
		scanf("%d%d%d", &p->icurr, &p->idata, &p->inext);
		
		if(p->icurr == temp)
		{
			back_o = insert_back(back_o, p);
			count_new++;
			temp = p->inext;
		}
		else
			back_i = insert_back(back_i, p);
	}
	
#ifdef DEBUG
	debug_print(&input, &output);
	printf("-------------------depart line-------------------\n");
#endif
	
	/*************************** create linked list ******************************/
	while(temp != -1)
	{
		p = input.next;
		while(p->icurr != temp)
			p = p->next;
		
		modify(p);
		back_o = insert_back(back_o, p);
		count_new++;
		temp = p->inext;
	}

#ifdef DEBUG
	debug_print(&input, &output);
	printf("count_new : %d\n", count_new);
	printf("-------------------depart line-------------------\n");
#endif

	count = count_new;

	/*************************** reverse linked list ******************************/
	k = 0;
	temp = count / rev;
	ptemp = p = output.next;

	array = (pnode*)malloc(sizeof(node) * count);

	for(i = 0; i < temp; i++)
	{
		p = ptemp;
		for(j = 0; j < rev-1; j++)
			p = p->next;

		ptemp = p->next;
		for(j = 0; j < rev; j++)
		{
			array[k++] = p;
			p = p->prev;
		}
	}
	while(ptemp != NULL)
	{
		array[k++] = ptemp;
		ptemp = ptemp->next;
	}

#ifdef DEBUG
	for(i = 0; i < count; i++)
		printf("%d: %d\n", i, array[i]->idata);
	printf("-------------------depart line-------------------\n");
#endif

	/*************************** print linked list ******************************/
	for(i = 0; i < count; i++)
	{
		p = array[i+1];
		ptemp = array[i];

		if(i == count-1)
			printf("%05d %d -1\n", ptemp->icurr, ptemp->idata);
		else
			printf("%05d %d %05d\n", ptemp->icurr, ptemp->idata, p->icurr);
	}

	return 0;
}


#ifdef DEBUG
void print_list(pnode head)
{
	while(head != NULL)
	{
		printf("%05d %d ", head->icurr, head->idata);
		
		if(head->inext != -1)
			printf("%05d\n", head->inext);
		else
			printf("-1\n");

		head = head->next;
	}
}

void debug_print(pnode input, pnode output)
{
	printf("----------DEBUG PRINT------------\n");
	printf("intput list:\n");
	print_list(input->next);
	printf("----------------------\n");
	printf("output list:\n");
	print_list(output->next);
}
#endif